package HASH_TABLE

// 回溯算法https://www.bilibili.com/video/BV1mG4y1A7Gu/?vd_source=3e5b8596fdf7a1e637fb85e996addeda
//var mapping = [...]string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
//
//func letterCombinations(digits string) (ans []string) {
//	n := len(digits)
//	if n == 0 {
//		return
//	}
//	path := make([]byte, n)
//	var dfs func(int)
//	dfs = func(i int) {
//		if i == n {
//			ans = append(ans, string(path))
//			return
//		}
//		for _, c := range mapping[digits[i]-'0'] {
//			path[i] = byte(c)
//			dfs(i + 1)
//		}
//	}
//	dfs(0)
//	return
//}
// 电话号码的字母组合：给定数字串，返回所有可能的字母组合
// 数字与字母的映射遵循传统电话键盘布局

// 定义数字到字母的映射表
// 使用数组而非map，因为索引可以直接对应数字，访问效率更高
// 索引0和1对应空字符串，因为数字0和1在电话键盘上没有对应的字母
var mapping = [...]string{
	"",     // 索引0，对应数字0
	"",     // 索引1，对应数字1
	"abc",  // 索引2，对应数字2
	"def",  // 索引3，对应数字3
	"ghi",  // 索引4，对应数字4
	"jkl",  // 索引5，对应数字5
	"mno",  // 索引6，对应数字6
	"pqrs", // 索引7，对应数字7
	"tuv",  // 索引8，对应数字8
	"wxyz", // 索引9，对应数字9
}

// letterCombinations 计算并返回数字串对应的所有可能字母组合
// 参数：digits 是仅包含2-9的数字字符串
// 返回值：所有可能的字母组合组成的字符串切片
func letterCombinations(digits string) (ans []string) {
	// 获取输入数字串的长度
	n := len(digits)

	// 边界条件处理：如果输入为空字符串，直接返回空切片
	if n == 0 {
		return
	}

	// 创建一个固定长度的字节切片，用于存储当前正在构建的字母组合
	// 长度等于输入数字串的长度，因为每个数字对应一个字母
	// 使用byte类型是因为Go中字符本质上是字节，操作更高效
	path := make([]byte, n)

	// 定义深度优先搜索(DFS)函数，用于递归构建字母组合
	// 参数i表示当前正在处理第i个数字(从0开始计数)
	var dfs func(int)
	dfs = func(i int) {
		// 递归终止条件：当处理到第n个数字时(i == n)
		// 说明已经为所有数字选择了对应的字母，完成了一个组合
		if i == n {
			// 将当前path字节切片转换为字符串，添加到结果切片中
			// string()函数会创建一个新的字符串，不会影响原path
			ans = append(ans, string(path))
			return
		}

		// 获取当前数字对应的字符(如digits[i]是'2')
		// 减去'0'得到对应的整数(如'2'-'0'=2)
		digit := digits[i] - '0'

		// 遍历当前数字对应的所有字母(如数字2对应"abc")
		// range遍历字符串时，会返回每个字符的Unicode码点
		for _, c := range mapping[digit] {
			// 将当前字母存入path的第i个位置
			// 这里直接覆盖而不是append，因为path长度固定
			// 这是一种优化，避免了动态扩容和回溯时的截断操作
			path[i] = byte(c)

			// 递归处理下一个数字(i+1)
			// 当递归返回时，会自动回到当前层，继续遍历下一个字母
			// 这就是回溯的过程，不需要显式的撤销操作
			dfs(i + 1)
		}
	}

	// 从第0个数字开始递归构建组合
	dfs(0)

	// 返回所有可能的字母组合
	return
}
